package dp

// https://leetcode-cn.com/problems/course-schedule/
// 解法: 广度优先搜索
// 更优的解法: 只要没有出现环，就不会有问题
// 当前: TL, 路径可能要先存入一个map 的数据结构中，减少重复查询次数
// 时间复杂度: O(n * log(n))
func CanFinish(numCourses int, prerequisites [][]int) bool {
	preMap := make(map[int][]int)
	posMarkMap := make(map[int]bool)
	historyPosMarkMap := make(map[int]bool)
	for _, currentRely := range prerequisites {
		if nil == preMap[currentRely[0]] {
			preMap[currentRely[0]] = make([]int, 0)
		}
		preMap[currentRely[0]] = append(preMap[currentRely[0]], currentRely[1])
	}
	for leftPos, rightPosArr := range preMap {
		posMarkMap[leftPos] = true
		for _, currentRightPos := range rightPosArr {
			if !recurForRelyRoute(currentRightPos, historyPosMarkMap, posMarkMap, preMap) {
				return false
			}
		}
		posMarkMap[leftPos] = false
		historyPosMarkMap[leftPos] = true
	}
	return true
}

// 递归方法: 遍历所有依赖关系，并确认是否有循环依赖的情况
// 没有循环依赖: 返回false
// currentPos: 当前遍历的位置
// preMarkMap: 已经遍历的 预检查项 下标
// posMarkMap: 已经遍历过的位置下标
func recurForRelyRoute(currentPos int, historyPosMarkMap map[int]bool, posMarkMap map[int]bool, preMap map[int][]int) bool {
	if posMarkMap[currentPos] {
		return false
	}
	// 剪枝，走过的分支就不用再走了，并且走过的分支一定是没有问题的
	if historyPosMarkMap[currentPos] {
		return true
	}
	posMarkMap[currentPos] = true
	if currentRightPosArr, ok := preMap[currentPos]; ok {
		for _, currentRightPos := range currentRightPosArr {
			if !recurForRelyRoute(currentRightPos, historyPosMarkMap, posMarkMap, preMap) {
				return false
			}
		}
	}
	posMarkMap[currentPos] = false
	historyPosMarkMap[currentPos] = true
	return true
}
